#region

using System.Collections;

#endregion

namespace AdvancedTraining.Lesson34;

/// <summary>
/// 扁平化嵌套列表迭代器
/// 本题测试链接 : https://leetcode.cn/problems/flatten-nested-list-iterator/
///
/// 设计一个迭代器，用于遍历嵌套的整数列表。
///
/// 算法思路：
/// 1. 使用栈来记录访问路径，实现深度优先遍历
/// 2. 通过栈的回溯机制，在需要时找到下一个整数
/// 3. 支持 hasNext() 和 next() 操作
/// 4. 时间复杂度：均摊O(1)，空间复杂度：O(深度)
/// </summary>
public class FlattenNestedListIterator //leetcode_0341
{
    /// <summary>
    /// 嵌套整数接口
    /// 不要提交这个接口类，这是题目给定的接口
    /// </summary>
    public interface INestedInteger
    {
        /// <summary>
        /// 如果此NestedInteger包含单个整数而不是嵌套列表，则返回true
        /// </summary>
        bool IsInteger();

        /// <summary>
        /// 如果此NestedInteger包含单个整数，则返回该整数
        /// 如果此NestedInteger包含嵌套列表，则返回null
        /// </summary>
        int? GetInteger();

        /// <summary>
        /// 如果此NestedInteger包含嵌套列表，则返回该列表
        /// 如果此NestedInteger包含单个整数，则返回null
        /// </summary>
        IList<INestedInteger> GetList();
    }

    /// <summary>
    /// 嵌套列表迭代器实现
    /// </summary>
    public class NestedIterator
    {
        private readonly IList<INestedInteger> _list;
        private readonly Stack<int> _stack;
        private bool _used;

        /// <summary>
        /// 构造函数，初始化迭代器
        /// </summary>
        /// <param name="nestedList">嵌套列表</param>
        public NestedIterator(IList<INestedInteger> nestedList)
        {
            _list = nestedList;
            _stack = new Stack<int>();
            _stack.Push(-1);
            _used = true;
            HasNext();
        }

        /// <summary>
        /// 返回下一个整数
        /// </summary>
        /// <returns>下一个整数，如果没有则返回null</returns>
        public int? Next()
        {
            int? ans = null;
            if (!_used)
            {
                ans = Get(_list, _stack);
                _used = true;
                HasNext();
            }
            return ans;
        }

        /// <summary>
        /// 检查是否还有下一个整数
        /// </summary>
        /// <returns>如果还有下一个整数返回true，否则返回false</returns>
        public bool HasNext()
        {
            if (_stack.Count == 0) return false;
            if (!_used) return true;
            if (FindNext(_list, _stack)) _used = false;
            return !_used;
        }

        /// <summary>
        /// 根据栈中的路径获取对应的整数
        /// </summary>
        /// <param name="nestedList">当前嵌套列表</param>
        /// <param name="stack">访问路径栈</param>
        /// <returns>找到的整数</returns>
        private int? Get(IList<INestedInteger> nestedList, Stack<int> stack)
        {
            var index = stack.Pop();
            int? ans = null;
            if (stack.Count > 0)
                ans = Get(nestedList[index].GetList(), stack);
            else
                ans = nestedList[index].GetInteger();
            stack.Push(index);
            return ans;
        }

        /// <summary>
        /// 查找下一个整数的位置
        /// </summary>
        /// <param name="nestedList">当前嵌套列表</param>
        /// <param name="stack">访问路径栈</param>
        /// <returns>是否找到下一个整数</returns>
        private bool FindNext(IList<INestedInteger> nestedList, Stack<int> stack)
        {
            var index = stack.Pop();
            if (stack.Count > 0 && FindNext(nestedList[index].GetList(), stack))
            {
                stack.Push(index);
                return true;
            }

            for (var i = index + 1; i < nestedList.Count; i++)
                if (PickFirst(nestedList[i], i, stack))
                    return true;
            return false;
        }

        /// <summary>
        /// 从指定位置开始寻找第一个整数
        /// </summary>
        /// <param name="nested">嵌套整数</param>
        /// <param name="position">位置</param>
        /// <param name="stack">访问路径栈</param>
        /// <returns>是否找到整数</returns>
        private bool PickFirst(INestedInteger nested, int position, Stack<int> stack)
        {
            if (nested.IsInteger())
            {
                stack.Push(position);
                return true;
            }

            var actualList = nested.GetList();
            for (var i = 0; i < actualList.Count; i++)
                if (PickFirst(actualList[i], i, stack))
                {
                    stack.Push(position);
                    return true;
                }

            return false;
        }
    }

    /// <summary>
    /// 嵌套整数的具体实现类（用于测试）
    /// </summary>
    public class NestedIntegerImpl : INestedInteger
    {
        private readonly int? _value;
        private readonly IList<INestedInteger> _list;

        /// <summary>
        /// 构造一个整数类型的嵌套整数
        /// </summary>
        /// <param name="value">整数值</param>
        public NestedIntegerImpl(int value)
        {
            _value = value;
            _list = null;
        }

        /// <summary>
        /// 构造一个列表类型的嵌套整数
        /// </summary>
        /// <param name="list">嵌套列表</param>
        public NestedIntegerImpl(IList<INestedInteger> list)
        {
            _value = null;
            _list = list;
        }

        /// <summary>
        /// 判断是否为整数
        /// </summary>
        /// <returns>如果是整数返回true，否则返回false</returns>
        public bool IsInteger()
        {
            return _value.HasValue;
        }

        /// <summary>
        /// 获取整数值
        /// </summary>
        /// <returns>整数值，如果不是整数则返回null</returns>
        public int? GetInteger()
        {
            return _value;
        }

        /// <summary>
        /// 获取嵌套列表
        /// </summary>
        /// <returns>嵌套列表，如果是整数则返回null</returns>
        public IList<INestedInteger> GetList()
        {
            return _list;
        }
    }

    /// <summary>
    /// 测试扁平化嵌套列表迭代器
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("扁平化嵌套列表迭代器算法测试开始");

        // 测试用例1: [[1,1],2,[1,1]]
        Console.WriteLine("测试用例1: [[1,1],2,[1,1]]");
        var list1 = new List<INestedInteger>
        {
            new NestedIntegerImpl(new List<INestedInteger>
            {
                new NestedIntegerImpl(1),
                new NestedIntegerImpl(1)
            }),
            new NestedIntegerImpl(2),
            new NestedIntegerImpl(new List<INestedInteger>
            {
                new NestedIntegerImpl(1),
                new NestedIntegerImpl(1)
            })
        };

        var iterator1 = new NestedIterator(list1);
        var result1 = new List<int>();
        while (iterator1.HasNext())
        {
            var next = iterator1.Next();
            if (next.HasValue)
                result1.Add(next.Value);
        }
        Console.WriteLine($"迭代结果: [{string.Join(",", result1)}] (期望: [1,1,2,1,1])");

        // 测试用例2: [1,[4,[6]]]
        Console.WriteLine("\n测试用例2: [1,[4,[6]]]");
        var list2 = new List<INestedInteger>
        {
            new NestedIntegerImpl(1),
            new NestedIntegerImpl(new List<INestedInteger>
            {
                new NestedIntegerImpl(4),
                new NestedIntegerImpl(new List<INestedInteger>
                {
                    new NestedIntegerImpl(6)
                })
            })
        };

        var iterator2 = new NestedIterator(list2);
        var result2 = new List<int>();
        while (iterator2.HasNext())
        {
            var next = iterator2.Next();
            if (next.HasValue)
                result2.Add(next.Value);
        }
        Console.WriteLine($"迭代结果: [{string.Join(",", result2)}] (期望: [1,4,6])");

        // 测试用例3: 空列表
        Console.WriteLine("\n测试用例3: 空列表");
        var list3 = new List<INestedInteger>();
        var iterator3 = new NestedIterator(list3);
        var result3 = new List<int>();
        while (iterator3.HasNext())
        {
            var next = iterator3.Next();
            if (next.HasValue)
                result3.Add(next.Value);
        }
        Console.WriteLine($"迭代结果: [{string.Join(",", result3)}] (期望: [])");

        // 测试用例4: 单个整数
        Console.WriteLine("\n测试用例4: 单个整数");
        var list4 = new List<INestedInteger>
        {
            new NestedIntegerImpl(42)
        };
        var iterator4 = new NestedIterator(list4);
        var result4 = new List<int>();
        while (iterator4.HasNext())
        {
            var next = iterator4.Next();
            if (next.HasValue)
                result4.Add(next.Value);
        }
        Console.WriteLine($"迭代结果: [{string.Join(",", result4)}] (期望: [42])");

        // 测试用例5: 深度嵌套 [1,2,[3,[4,[5,6]],7],8]
        Console.WriteLine("\n测试用例5: 深度嵌套 [1,2,[3,[4,[5,6]],7],8]");
        var list5 = new List<INestedInteger>
        {
            new NestedIntegerImpl(1),
            new NestedIntegerImpl(2),
            new NestedIntegerImpl(new List<INestedInteger>
            {
                new NestedIntegerImpl(3),
                new NestedIntegerImpl(new List<INestedInteger>
                {
                    new NestedIntegerImpl(4),
                    new NestedIntegerImpl(new List<INestedInteger>
                    {
                        new NestedIntegerImpl(5),
                        new NestedIntegerImpl(6)
                    })
                }),
                new NestedIntegerImpl(7)
            }),
            new NestedIntegerImpl(8)
        };

        var iterator5 = new NestedIterator(list5);
        var result5 = new List<int>();
        while (iterator5.HasNext())
        {
            var next = iterator5.Next();
            if (next.HasValue)
                result5.Add(next.Value);
        }
        Console.WriteLine($"迭代结果: [{string.Join(",", result5)}] (期望: [1,2,3,4,5,6,7,8])");

        Console.WriteLine("\n扁平化嵌套列表迭代器算法测试结束");
    }
}